백준 30804번

오늘 풀어본 문제는 백준의 30804번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 3

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

은하는 긴 막대에 $N$ 개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 $1$ 부터 $9$ 까지의 번호가 붙어있고, 앞쪽부터 차례로 $S_1, S_2, \cdots, S_N$ 번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.

탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 $a$ 개, 뒤에서 $b$ 개의 과일을 빼면 $S_{a+1}, S_{a+2}, \cdots, S_{N-b-1}, S_{N-b}$ 번 과일, 총 $N-(a+b)$ 개가 꽂혀있는 탕후루가 됩니다. $(0 \le a, b;$ $a+b < N)$

이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.

입력

첫 줄에 과일의 개수 $N$ 이 주어집니다. $(1 \le N \le 200\,000)$

둘째 줄에 탕후루에 꽂힌 과일을 의미하는 $N$ 개의 정수 $S_1, \cdots, S_N$ 이 공백으로 구분되어 주어집니다. $(1 \le S_i \le 9)$

출력

문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.

풀이과정

1번째 시도

문제를 해결하기 위해서 사용한 방식은 투 포인터 알고리즘이다.

start 포인터와 end 포인터를 두고, end 포인터가 ‘부분 탕후루’의 마지막 과일이라고 두었을 때 주어진 조건을 만족하는 가장 긴 부분 탕후루를 구성하도록 start 포인터를 옮기도록 하였다. end 포인터는 계속해서 한 칸씩 뒤로 밀며, start 포인터가 이에 맞춰 움직인 후에 구성된 부분 탕후루의 길이 중 최대값을 저장하는 방식으로 문제 해결을 시도하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int N;
    cin >> N;
    
    vector<int> S(N);
    
    for (int i=0; i<N; i++) {
        cin >> S[i];
        S[i]--;
    }
    
    int result = 0;
    
    int start = 0;
    int end = 0;
    
    int fruitUsed[9] = {0,};
    fruitUsed[S[start]] = 1;
    
    int fruitKindsCount = 1;
    
    while (end < N - 1) {
        end++;
        fruitUsed[S[end]]++;
        
        if (fruitUsed[S[end]] == 1) {
            fruitKindsCount++;
            
            if (fruitKindsCount > 2) {
                do {
                    fruitUsed[S[start]]--;
                    start++;
                } while (fruitUsed[S[start - 1]] > 0);
                
                fruitKindsCount--;
            }
        }
        
        result = max(result, end - start + 1);
    }
    
    cout << result;
    
    return 0;
}

실행 결과 ‘틀렸습니다’ 가 떴다.

2번째 시도

과일이 한 개만 있을 때 반복문이 실행되지 않아 오답인 0을 출력하는 현상을 발견하게 되었다. 초기 최댓값을 1로 설정하여 이 문제를 해결할 수 있을 것이라고 생각하였다.

코드는 다음과 같이 수정하였다.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int N;
    cin >> N;
    
    vector<int> S(N);
    
    for (int i=0; i<N; i++) {
        cin >> S[i];
        S[i]--;
    }
    
    int result = 1;
    
    int start = 0;
    int end = 0;
    
    int fruitUsed[9] = {0,};
    fruitUsed[S[start]] = 1;
    
    int fruitKindsCount = 1;
    
    while (end < N - 1) {
        end++;
        fruitUsed[S[end]]++;
        
        if (fruitUsed[S[end]] == 1) {
            fruitKindsCount++;
            
            if (fruitKindsCount > 2) {
                do {
                    fruitUsed[S[start]]--;
                    start++;
                } while (fruitUsed[S[start - 1]] > 0);
                
                fruitKindsCount--;
            }
        }
        
        result = max(result, end - start + 1);
    }
    
    cout << result;
    
    return 0;
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

간만에 투 포인터를 활용해볼 수 있던 어렵고 신기하고 재밌는 문제였다. 문제를 풀다보니 탕후루가 먹고 싶어졌지만, 군대 안이라 쉽지는 않을 것 같다. 다음 평일 외출때 먹으면 좋을지도 모르겠다!

그리고 솔브드 업데이트로 인해 뺏겼던 금장을 다시 되찾는데 성공하였다!

CLASS 3 MASTER

역시 금장이 있어야 마음이 편안해지는 것 같다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/30804

← Previous Post Next Post →